package com.lzp.leetcode.dp.simple;

/**
 * 最大子序列和
 *
 * @author lzp
 * @date 2020/7/8
 */
public class LC53_MaxSubArray {
    /**
     * 动态规划解法
     * <p>
     * n / n
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        // 定义状态数组
        int[] f = new int[n];

        // 初始化
        f[0] = nums[0];
        int ret = nums[0];

        // 迭代更新各个状态的值
        for (int i = 1; i < n; i++) {
            // 转移方程
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
            // 维护最小值
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}
